﻿using System;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Collections.Generic;

namespace IKE_painter
{
    public class Dijkstra
    {
        private int rank = 0;
        private int[,] L;
        private int[] C;
        public int[] D;
        private int trank = 0;

        public Dijkstra(int paramRank, int[,] paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++)
                {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            {
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0)
                {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue + L[minNode, i];
            }
        }
        public String Run()
        {
            String ret = "";
            for (trank = 1; trank < rank; trank++)
            {
                DijkstraSolving();
                ret += ("iteration " + trank) + "\n";
                for (int i = 0; i < rank; i++)
                    ret += (D[i] + "|");
                ret += ("\n");
                for (int i = 0; i < rank; i++)
                    ret += (C[i] + "|");
                ret += ("\n");
                ret += ("\n");
            }
            return ret;
        }
        //static void Main(string[] args)
        //{
        //    int[,] L ={
        //        {-1,  5, -1, -1, -1,  3, -1, -1}, 
        //        { 5, -1,  2, -1, -1, -1,  3, -1}, 
        //        {-1,  2, -1,  6, -1, -1, -1, 10}, 
        //        {-1, -1,  6, -1,  3, -1, -1, -1},
        //        {-1, -1, -1,  3, -1,  8, -1,  5}, 
        //        { 3, -1, -1, -1,  8, -1,  7, -1}, 
        //        {-1,  3, -1, -1, -1,  7, -1,  2}, 
        //        {-1, -1, 10, -1,  5, -1,  2, -1} 
        //    };
        //    Dijkstra clss = new Dijkstra((int)Math.Sqrt(L.Length), L);
        //    clss.Run();
        //    Console.WriteLine("Solution is");
        //    foreach (int i in clss.D)
        //    {
        //        Console.WriteLine(i);
        //    }
        //    Console.WriteLine("Press Enter for exit.");
        // //   Console.Read();
        //}

        // Floyd-Warshall algorithm
        // 
        //  solves the all-pairs shortest path problem using Floyd-Warshall algorithm
        //  inputs:  nn, number of nodes
        //           connectivity matrix cmat, where 0 means disconnected
        //             and distances are all positive.  array of doubles of
        //             length (nn*nn).
        //  outputs: 
        //           dist_mat - shortest path distances(the answer)
        //           pred_mat - predicate matrix, useful in reconstructing shortest routes
        //           Note that the caller should provide empty pointers as this 
        //           function will handle the malloc() calls.

        //void fwarsh(int nn, double* cmat, double** dist_mat, int** pred_mat)
        //{
        //    double* dist;
        //    int* pred;
        //    int i, j, k; //loop counters

        //    //initialize data structures
        //    dist = (double*)malloc(sizeof(double) * nn * nn);
        //    pred = (int*)malloc(sizeof(int) * nn * nn);
        //    memset(dist, 0, sizeof(double) * nn * nn);
        //    memset(pred, 0, sizeof(int) * nn * nn);

        //    //algorithm initialization
        //    for (i = 0; i < nn; i++)
        //    {
        //        for (j = 0; j < nn; j++)
        //        {
        //            if (cmat[i * nn + j] != 0.0)
        //                dist[i * nn + j] = cmat[i * nn + j];
        //            else
        //                dist[i * nn + j] = HUGE_VAL; //disconnected

        //            if (i == j)  //diagonal case
        //                dist[i * nn + j] = 0;

        //            if ((dist[i * nn + j] > 0.0) && (dist[i * nn + j] < HUGE_VAL))
        //                pred[i * nn + j] = i;
        //        }
        //    }

        //    //Main loop of the algorithm
        //    for (k = 0; k < nn; k++)
        //    {
        //        for (i = 0; i < nn; i++)
        //        {
        //            for (j = 0; j < nn; j++)
        //            {
        //                if (dist[i * nn + j] > (dist[i * nn + k] + dist[k * nn + j]))
        //                {
        //                    dist[i * nn + j] = dist[i * nn + k] + dist[k * nn + j];
        //                    pred[i * nn + j] = k;
        //                    //printf("updated entry %d,%d with %d\n", i,j, dist[i*nn+j]);
        //                }
        //            }
        //        }
        //    }

        //    /* //Print out the results table of shortest distances
        //    for (i=0; i < nn; i++) {
        //      for (j=0; j < nn; j++)
        //        printf("%g ", dist[i*nn+j]);
        //      printf("\n");
        //      } */

        //    //now set the dist and pred matrices for the calling function
        //    //but do some checks because we allow NULL to be passed if the user
        //    //doesn't care about one of the results.
        //    if (dist_mat)
        //        *dist_mat = dist;
        //    else
        //        free(dist);

        //    if (pred_mat)
        //        *pred_mat = pred;
        //    else
        //        free(pred);

        //    return;
        //}  //end of fwarsh()

    }
}
